class Solution
{
public:
    // 和相加不同的是，这题如果从前往后，会有后效性存在，因为如果当前数是负数，并且后面
    // 还有负数，那么就可以让负数变成正数
    // 那么，该如何去处理呢？
    enum
    {
        N = 20010
    };
    int f[N], g[N];
    int maxProduct(vector<int> &nums)
    {
        // 乘积最大可能由上一个的乘积最小得出
        f[0] = g[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.size(); ++i)
        {
            int a = f[i - 1] * nums[i];
            int b = g[i - 1] * nums[i];
            f[i] = max(nums[i], max(a, b));
            g[i] = min(nums[i], min(a, b));
            res = max(res, f[i]);
        }
        return res;
    }
};